package DynamicProgramming;//给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于
//difference 。 
//
// 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：arr = [1,2,3,4], difference = 1
//输出：4
//解释：最长的等差子序列是 [1,2,3,4]。 
//
// 示例 2： 
//
// 
//输入：arr = [1,3,5,7], difference = 1
//输出：1
//解释：最长的等差子序列是任意单个元素。
// 
//
// 示例 3： 
//
// 
//输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
//输出：4
//解释：最长的等差子序列是 [7,5,3,1]。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 10⁵ 
// -10⁴ <= arr[i], difference <= 10⁴ 
// 
// Related Topics 数组 哈希表 动态规划 👍 179 👎 0


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class longestSubsequence {
    public int longestSubsequence(int[] arr, int difference) {

        int n = arr.length;
        if(n<2){
            return n;
        }
        /**
         * map结合动态规划
         * */
        Map<Integer, Integer> map = new HashMap<>();
        map.put(arr[0], 1);
        for (int i = 1; i < n; i++) {
            if (map.containsKey(arr[i]-difference)){
                //如果集合中已经有等差的上一个值了,则当前值为上一个值的value+1
                map.put(arr[i], map.get(arr[i]-difference)+1);
            } else {
                map.put(arr[i],1);
            }
        }
        int maxLen = 0;
        //最后从value中找个最大的
        for (int i: map.keySet()) {
            maxLen = Math.max(maxLen, map.get(i));
        }
        return maxLen;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
